1. Field of the Invention
Embodiments of the present invention relate generally to computer systems. More particularly, embodiments of the present invention relate to a system and method for assigning basic blocks to computer control flow paths of a computer program in a computer-based environment.
2. Description of the Background Art
Work has been performed in the area of predicated execution for computer programs. A published algorithm for branch elimination exists in a Ph.D, dissertation entitled Exploiting Instruction-Level Parallelism in the Presence of Conditional Branches to Scott A. Mahlke, Department of Electrical and Computer Engineering, University of Illinois, Urbana, Ill., September, 1996, fully incorporated herein by reference thereto. The object of Mahlke's approach is to merge as many control flow paths together to form “hyperblocks” that are as large as possible. A “Hyperblock”, as defined by Mahlke, is a collection of connected basic blocks in which control may only enter through the first block, referred to as the entry block. Control flow may leave from any number of blocks in the hyperblock. All control flow between basic blocks in a hyperblock is removed via if-conversion. The goal of hyperblocks is to intelligently group basic blocks from many different control flow paths into a single manageable block for compiler optimization and scheduling. The formation of hyperblocks is necessary for Mahlke's approach because the IMPACT compiler in which Mahlke's approach was implemented does not contain an instruction scheduler capable of cross basic block code motion.
In order to achieve a desired combined path, Mahlke's algorithm actually enumerates all possible control flow paths through the scheduling region of the computer program and computes a priority function for each control flow path. A disadvantage to Mahlke's approach is that it has to find all possible control flow paths, the number of which is proportional to the square of the number of split or bifurcation points in the region.
Another disadvantage of Mahlke's approach is that his aggressive if-conversion routine actually results in an over subscription of computer resources. As an attempt to solve this problem, David I. August, Wen-mei W. Hwu, and Scott A. Mahlke, in an article entitled A Framework for Balancing Control Flow and Predication, published for the Proceedings of the 30th International Symposium on Microarchitecture, December, 1997, and fully incorporated herein by reference thereto, propose a technique that involves iteratively removing control flow paths and rescheduling hyperblocks until the resources are no longer over subscribed. Such a computer technique is computer-time consuming and is therefore not practical.